package sort

import (
	"container/heap"
	"sort"
)

type IntHeap struct {
	sort.IntSlice
}

func (h *IntHeap) Pop() any {
	old := h.IntSlice[h.Len()-1]
	h.IntSlice = h.IntSlice[:h.Len()-1]
	return old
}

func (h *IntHeap) Push(x any) {
	e := x.(int)
	h.IntSlice = append(h.IntSlice, e)
}

func HeapSort(nums []int) []int {
	var res = make([]int, len(nums))

	ih := &IntHeap{IntSlice: nums}
	heap.Init(ih)

	for i := 0; i < len(nums); i++ {
		e := heap.Pop(ih).(int)
		res[i] = e
	}
	return res
}
